/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> get_money(TreeNode *cur) {
        if (cur == nullptr) return vector<int> {0, 0};
        vector<int> left_dp = get_money(cur->left);
        vector<int> right_dp = get_money(cur->right);
        vector<int> dp(2);
        //dp[0]：不偷当前节点， dp[1]：偷当前节点
        dp[0] = max(left_dp[0], left_dp[1]) + max(right_dp[0], right_dp[1]);
        dp[1] = cur->val + left_dp[0] + right_dp[0];
        return dp;
    }
    int rob(TreeNode* root) {
        vector<int> result = get_money(root);
        return max(result[0], result[1]);
    }
};
